class Solution {
public:
    int waysToStep(int n)
    {
        long long result = 0;
        long long a = 1, b = 2, c = 4;

        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;

        for (int i = 3; i < n; i++)
        {
            result = (a + b + c) % 1000000007;
            a = b % 1000000007;
            b = c % 1000000007;
            c = result % 1000000007;
        }

        return result;

    }
};